package formal.string;

import java.util.ArrayList;

/**
 * @author DengYuan2
 * @create 2021-02-03 20:24
 */
public class E_696 {
    public static void main(String[] args) {
//        String s = "00110011";
//        String s = "10101";
        String s = "1010001";
//        String s = "00110";
        int res = countBinarySubstrings2(s);
        System.out.println(res);
    }


    /**
     * 我的写法太乱了，而且时间过长，系统没法判断
     * 下面是大神的写法
     * 思想-pre为前面数字A的最大连续长度，curLen为现在数字B的现在长度
     *
     * @param s
     * @return
     */
    public static int countBinarySubstrings(String s) {
        int pre = 0, curLen = 1, cnt = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                curLen++;
            } else {
                pre = curLen;
                curLen = 1;
            }
            if (pre >= curLen) {
                cnt++;
            }
        }
        return cnt;
    }

    /**
     * 官方-记录每个数字的连续段长度
     * 思路： https://leetcode-cn.com/problems/count-binary-substrings/solution/ji-shu-er-jin-zhi-zi-chuan-by-leetcode-solution/
     *
     * @param s
     * @return
     */
    public static int countBinarySubstrings2(String s) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < s.length(); ) {
            int count = 1;
            int c = s.charAt(i);
            int j = i + 1;
            while (j < s.length() && c == s.charAt(j)) {
                count++;
                j++;
            }
            list.add(count);
            i = j;
        }
        int res = 0;
        for (int i = 1; i < list.size(); i++) {
            res += Math.min(list.get(i), list.get(i - 1));
        }
        return res;
    }

    /**
     * 官方继续做了优化，感觉比大神的好理解一些，也快了一些
     *
     * @param s
     * @return
     */
    public static int countBinarySubstrings3(String s) {
        int res = 0;
        int pre = 0;
        int i = 0;
        int j = s.length();
        while (i < j) {
            char cur = s.charAt(i);
            int x = i + 1;
            int count = 1;
            while (x < s.length() && cur == s.charAt(x)) {
                count++;
                x++;
            }
            res += Math.min(pre, count);
            pre =count;
            i=x;
        }
        return res;
    }
}
